package com.some;

public class Dijkstra_test {
    public static final int M = 10000; // 代表正无穷

    public static void main(String[] args) {
        // 二维数组每一行分别是 A、B、C、D、E 各点到其余点的距离,
        // A -> A 距离为0, 常量M 为正无穷
        int[][] weight1 = {
                {0, 4, M, 2, M},
                {4, 0, 4, 1, M},
                {M, 4, 0, 1, 3},
                {2, 1, 1, 0, 7},
                {M, M, 3, 7, 0}
        };

        int start = 0;

        int[] shortPath = dijkstra(weight1, start);

        for (int i = 0; i < shortPath.length; i++)
            System.out.println("从" + start + "出发到" + i + "的最短距离为：" + shortPath[i]);
    }

    private static int[] dijkstra(int[][] weight1, int start) {
        int n = weight1.length;
        int[] shortPath = new int[n];
        int[] isVisit = new int[n];

        shortPath[start] = 0;
        isVisit[start] = 1;

        for (int count = 1; count < n; count++) {
            int k = -1;
            int dmin = Integer.MAX_VALUE;

            for (int i = 0; i < n; i++) {
                if (isVisit[i] == 0 && weight1[start][i] < dmin) {
                    k = i;
                    dmin = weight1[start][i];
                }
            }

            shortPath[k] = dmin;
            isVisit[k] = 1;

            for (int i = 0; i < n; i++) {
                if (isVisit[i] == 0 && shortPath[k] + weight1[k][i] < weight1[start][i]) {
                    weight1[start][i] = shortPath[k] + weight1[k][i];
                }
            }
        }
        return shortPath;
    }

}

/*
* 算法思路
1. 指定一个节点，例如我们要计算 'A' 到其他节点的最短路径
2. 引入两个集合（S、U），S集合包含已求出的最短路径的点（以及相应的最短长度），U集合包含未求出最短路径的点（以及A到该点的路径，注意 如上图所示，A->C由于没有直接相连 初始时为∞）
3. 初始化两个集合，S集合初始时 只有当前要计算的节点，A->A = 0，U集合初始时为 A->B = 4, A->C = ∞, A->D = 2, A->E = ∞，敲黑板！！！接下来要进行核心两步骤了
4. 从U集合中找出路径最短的点，加入S集合，例如 A->D = 2
5. 更新U集合路径，if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' ) 则更新U
6.循环执行 4、5 两步骤，直至遍历结束，得到A 到其他节点的最短路径

作者：殷天文
链接：https://www.jianshu.com/p/ff6db00ad866
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
* */
